/*
 * @lc app=leetcode.cn id=35 lang=golang
 * @lcpr version=30118
 *
 * [35] 搜索插入位置
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start
func searchInsert(nums []int, target int) int {
	i, j := 0, len(nums)-1

	for i < j {
		mid := (i + j) / 2
		if target > nums[mid] {
			i = mid + 1
		} else if target == nums[mid] {
			return mid
		} else {
			j = mid - 1
		}
	}

	if target <= nums[i] {
		return i
	} else {
		return j + 1
	}
}

// @lc code=end

/*
// @lcpr case=start
// [1,3,5,6]\n5\n
// @lcpr case=end

// @lcpr case=start
// [1,3,5,6]\n2\n
// @lcpr case=end

// @lcpr case=start
// [1,3,5,6]\n7\n
// @lcpr case=end

*/

